package 链表.删除链表中的重复元素2;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/5/9 15:37
 * @description:给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(1,new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))))));
        System.out.println(test(head));
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode root = new ListNode();
        root.next = head;
        ListNode p = head,pre = root;
        /**
         * key -> node.val; value -> node.val = key的节点个数
         */
        Map<Integer,Integer> map = new HashMap<>();
        while (p != null) {
            ListNode q = p.next;
            map.put(p.val,map.getOrDefault(p.val,0) + 1);
            p = q;
        }
        List<Integer> collect = map.entrySet().stream().filter(item -> item.getValue() > 1).map(Map.Entry::getKey).collect(Collectors.toList());
        p = head;
        while (p != null) {
            ListNode q = p.next;
            if (collect.contains(p.val)) {
                pre.next = p.next;
                p.next = null;
            } else {
                pre = pre.next;
            }
            p = q;
        }
        return root.next;
    }


    /**
     * 虚拟头节点 + 遍历
     * <p>
     * 时间复杂度：O(n)，其中 n 是链表的长度。 <br/>
     * 空间复杂度：O(1)
     */
    public static ListNode deleteDuplicates2(ListNode head) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode pre = dummyHead, cur = pre.next;
        while (cur != null) {
            ListNode next = cur.next;
            while (next != null && cur.val == next.val) {
                next = next.next;
            }
            if (next != cur.next) {
                //next 移动过，说明中间存在重复元素，将 pre 的 next 指针指向
                //当前的 next，这样就跳过了重复元素
                pre.next = next;
                cur = next;
            } else {
                //next 没有移动过，pre 和 cur 向后移动一位
                pre = cur;
                cur = next;
            }
        }
        return dummyHead.next;
    }


    //高效解法 TODO 和删除链表重复元素1这个题目思想一致
    public static ListNode delete(ListNode head) {
        ListNode root = new ListNode(-1,head);
        ListNode pre = root,p = root.next;
        while (p != null) {
            ListNode q = p.next;
            while (q != null && p.val == q.val) {
                q = q.next;
            }
            if (p.next != q) {
                //这时说明q移动过 将pre直接瞬移到q前面,然后让p指向q，相当于跳过了中间所有重复元素
                pre.next = q;
                p = q;
            } else {
                pre = p;
                p = p.next;
            }
        }
        return root.next;
    }

    public static ListNode test(ListNode head) {
        //TODO 这里定义了头结点root，所以最后的返回结果应该也是root.next而不是head。不用错误的任务二者是等价的
        ListNode root = new ListNode(-1,head);
        root.next = head;
        ListNode pre = root;
        ListNode p = pre.next;
        if (p == null || p.next == null) {
            return p;
        }
        while (p != null) {
            ListNode q = p.next;
            while (q != null && q.val == p.val) {
                q = q.next;
            }
            if (q != p.next) {
                pre.next = q;
                p = q;
            } else {
                pre = p;
                p = p.next;
            }
        }
        return root.next;
    }
}
